import java.lang.reflect.Array;
import java.util.LinkedList;
import java.util.Random;


public class Sort
{

    /**
     * Implement insertion sort.
     *
     * It should be:
     *  inplace
     *  stable
     *
     * Have a worst case running time of:
     *  O(n^2)
     *
     * And a best case running time of:
     *  O(n)
     *
     * @param arr
     */
    public static <T extends Comparable<T>> void insertionsort(T[] arr)
    {
        for(int i = 0; i< arr.length; i++)
        {
            T curr = arr[i];
            int j = i;
            while( (j>0)&& arr[j-1].compareTo(curr) > 0)
            {
                arr[j]=arr[j-1];
                j--;
            }
            arr[j]=curr;
        }
    }

    /**
     * Implement quick sort.
     *
     * Use the provided random object to select your pivots.
     * For example if you need a pivot between a (inclusive)
     * and b (exclusive) where b > a, use the following code:
     *
     * int pivotIndex = r.nextInt(b - a) + a;
     *
     * It should be:
     *  inplace
     *
     * Have a worst case running time of:
     *  O(n^2)
     *
     * And a best case running time of:
     *  O(n log n)
     *
     * @param arr
     */
    public static <T extends Comparable<T>> void quicksort(T[] arr, Random r)
    {
        quicksortHelper(arr, r, 0, arr.length - 1);
    }

    public static <T extends Comparable<T>>void quicksortHelper(T[] array,Random rand, int beg, int end)
    {
        int i = beg;
        int j = end;

        //calculate random pivot
        //if there is nothing to sort, return
        if(beg == end)
        {
            return;
        }
        int pivotIndex =rand.nextInt(end - beg) + beg;
        T pivot = array[pivotIndex];

        while (i <= j)
        {
            //get i in the right position
            while (array[i].compareTo(pivot)<0)
            {
                i++;
            }
            //get j in the right position
            while (array[j].compareTo(pivot)>0)
            {
                j--;
            }
            //swap i and j if they have not overlapped
            if (i <= j)
            {
                T iVal = array[i];
                array[i] = array[j];
                array[j] = iVal;
                i++;
                j--;
            }
        }

        //if i is still in the middle of the list and not at one of the ends, then recursively sort the two halves
        if (beg < i - 1)
        {
            quicksortHelper(array,rand, beg, i - 1);
        }
        if (i < end)
        {
            quicksortHelper(array,rand, i, end);
        }
    }

    /**
     * Implement merge sort.
     *
     * It should be:
     *  stable
     *
     * Have a worst case running time of:
     *  O(n log n)
     *
     * And a best case running time of:
     *  O(n log n)
     *
     * @param arr
     * @return
     */
    public static <T extends Comparable<T>> T[] mergesort(T[] arr)
    {
        T[] helper= (T[])Array.newInstance(arr.getClass().getComponentType(),arr.length);
        Sort.mergesortHelper(arr,helper,0,arr.length-1);
        return arr;
    }

    private static <T extends Comparable<T>>void mergesortHelper(T[] array, T[] workingArray, int beg, int end)
    {
        int middle;
        //if there's gonna be more than 1 element in the subarray
        if(beg < end)
        {
            //find the split point
            middle = (beg+end)/2;
            //divide up what's left of each half
            Sort.mergesortHelper(array, workingArray, beg, middle);
            Sort.mergesortHelper(array, workingArray, middle + 1, end);
            //merge the two halves
            Sort.merge(array,workingArray,beg,middle,end);
        }

    }
    private static <T extends Comparable<T>> void merge(T[] array, T[] workingArray, int beg, int mid, int end)
    {

        int aCounter = beg;
        int bCounter = mid+1;
        int i = beg;
        //move stuff down into the working array as you work through the A and B arrays.
        while ((aCounter <= mid) && (bCounter <= end))
        {
            if (array[aCounter].compareTo(array[bCounter])<=0)
            {
                workingArray[i] = array[aCounter];
                aCounter++;
            }
            else
            {
                workingArray[i] = array[bCounter];
                bCounter++;
            }
            i++;
        }
        //if you are done with the A array, dump te B array
        if (aCounter > mid)
        {
            for (int l=bCounter; l<=end; l++)
            {
                workingArray[i] = array[l]; i++;
            }
        }
        //if you are done with the B array, dump the A array
        else
        {   for (int m=aCounter; m<=mid; m++)
            {
                workingArray[i] = array[m]; i++;
            }
        }
        //copy over the working array into the real array
        for (int n=beg; n<=end; n++)
        {
            array[n] = workingArray[n];
        }
    }

    /**
     * Implement radix sort
     *
     * Hint: You can use Integer.toString to get a string
     * of the digits. Don't forget to account for negative
     * integers, they will have a '-' at the front of the
     * string.
     *
     * It should be:
     *  stable
     *
     * Have a worst case running time of:
     *  O(kn)
     *
     * And a best case running time of:
     *  O(kn)
     *
     * @param arr
     * @return
     */
    public static int[] radixsort(int[] arr)
    {
        boolean keepIterating = true;
        int decimalPlace = 1;

        //I have 11 buckets, 10 for the digits 0-9, and 1 for negative numbers, at the beginning
        LinkedList[] buckets = new LinkedList[11];
        for (int i = 0; i < 11; i++)
        {
            buckets[i] = new LinkedList();
        }

        while (keepIterating)
        {
            keepIterating = false;

            //assign each int a bucket based on the current decimal place
            for (int i = 0; i < arr.length; i++)
            {
                int index;
                String s =Integer.toString(arr[i]);
                if(s.length() >= decimalPlace)
                {
                    char c = s.charAt(s.length()-decimalPlace);
                    //place the negative numbers in bucket zero
                    if(c == '-')
                    {
                        index = 0;
                    }
                    else
                    {
                        index = Character.getNumericValue(c) + 1;
                    }
                }
                else
                {
                    index = 1;
                }
                if (index > 1)
                {
                    keepIterating = true;
                }
                buckets[index].addLast(new Integer(arr[i]));
            }
            decimalPlace++;

           //put everything back into the array
            int i = 0;
            //re-add of the negative numbers in reverse order.
            while (!buckets[0].isEmpty())
            {
                Integer negValue = (Integer) buckets[0].getLast();
                buckets[0].removeLast();
                arr[i++] = negValue.intValue();
            }

            for (int j = 1; j < 11; j++) //was 0,was 10
            {
                while (!buckets[j].isEmpty())
                {
                    Integer value = (Integer) buckets[j].getFirst();
                    buckets[j].removeFirst();
                    arr[i++] = value.intValue();
                }
            }
        }
        return arr;
    }
}